The present invention relates to a range check cell and a method for the use thereof in determining the range match of incoming data values in a database. The invention particularly relates to a range check cell which stores the Upper Limit and Lower Limit of a specified range and facilitates a range match on an incoming data value within one content addressable memory (CAM) operation.
The present invention relates to intelligent range check cells for use in coprocessors using the classless Inter domain routing protocol, which is a subset of the Internet protocol. More particularly, the present invention relates to intelligent range check cells, which can be used as building blocks for a database management system to enable matching of input data to a user determined range of stored data in the system. The present invention also relates to a method for retrieving data, from a plural range of stored data, which matches or is similar to input retrieval data.
In the field of information technology, the ability to store, obtain, process, retrieve and transfer data speedily and accurately is critical. Data can include voice, images, pictures, words or any combination thereof.
The necessity for faster and accurate transfer and retrieval of data has increased with the use of the Internet data communication. Data communication over the Internet is performed in accordance with a specific protocol. Each protocol specifies how the data is sent from the source point to the destination point.
The IP protocol governs the data and voice communication over the Internet. The CIDR protocol, which is a subset of the IP protocol, governs addressing over the Internet. Under the CIDR protocol, the correct destination address is the one that is associated with the longest prefix. Each Internet address in the CIDR protocol is associated with an IP address and a sub-net mask value. In each router, the routing tables are constructed out of prefix information and are searched using the destination address to determine the exit port of the router. According to the CIDR protocol, a sub-net mask value could only include a series of consecutive xe2x80x9c1sxe2x80x9d followed by xe2x80x9c0s.xe2x80x9d xe2x80x9c1xe2x80x9d represents that the corresponding bit in the associated IP address is used to determine the final physical address of the destination.
A transfer of information between two points begins by the user sending a packet of information to the receiver. Depending upon the location of the receiver, the information may have to travel through several networks before it reaches the receiver. It therefore, becomes very important that the information travels accurately through the shortest possible route from the sender to the receiver. It becomes all the more difficult since different destinations may have portions of their address in common with each other.
As the number of networks and destinations which are interconnected increases by the day, it is highly important that routers in each network are able to route the information as fast as possible to the final destination. The current technology takes a long time to determine the correct address in a router to route the information. For example, a 16 bit address could require up to 15 clock cycles to be determined in the currently available technology. In networks incorporating a wider address such as 128 bits, it would take more time to accurately determine the address of the final destination.
In computing or in everyday use of computers, it becomes essential to access databases to recover specific information of value. The need for speed of data recovery by the user is closely allied to the need for accuracy of results. One solution in the art to ensure speed and accuracy in the field of data recovery is to convert the applied data into a specific code and to match the applied code entry by entry with the data stored in the database. This process however, is in computing terms quite long drawn. This process works by matching the applied data with the data stored in the database in the form of a range.
The known solutions to the range match problem fall in two categories:
1. Sequential memory based: These solutions typically expand the range field and hence require either a huge memory or multiple accesses to the table.
2. CAM based: These solutions try to split the range search into multiple prefix searches and use a ternary CAM to do these searches. Hence multiple entries are required for each range value and multiple searches are also required.
Thus there is a need for a search cell capable of searching a database in the shortest possible time without compromising on the accuracy of the results.
The applicants"" own co-pending application Ser. No. 09/865,241 filed on May 24, 2001 overcomes many of the problems associated with the prior art and discloses a novel search cell for use as a building block of a database and which is capable of performing hierarchical searches in the database as well as a method thereof. The novel search cell of the co-pending application includes a plurality of Logic Content addressable Memory Cells (LCAMS) arranged in rows and columns. Each LCAM cell includes a first and second memory cells, a first comparator coupled to the first and second memory cells for comparing the content of the first memory cell with one bit of a test information. To search for a second data type entry, the search cell searches for the longest prefix entry belonging to the first data type by comparing test information with the entries stored in the first storage unit. Once the longest prefix entry is determined, a corresponding entry in the second storage unit is output as the output of the search cell. The contents of said U.S. patent application are deemed to have been incorporated herein by reference.
Content addressable memory cells are well known in the art and are used to compare a search word with a set of stored words. An indication of whether or not the search word matches the stored words is produced for each stored word. A distinguishing characteristic of a CAM is that each stored word is uniquely identified on the basis of the content of the word itself, rather than by its address within the memory array.
A CAM includes an array of memory cells arranged in a matrix of rows and columns. Each memory cell stores a single bit of digital information. The bits stored in a row of memory elements constitute a stored word. During a match operation, a search word of input data is applied to all the rows, and an indication is produced for each row as to whether or not the search word matches the word stored therein.
An important use for a CAM is to facilitate searches on a conventional indexed random access memory (RAM). The CAM stores a series of xe2x80x9ctagsxe2x80x9d which represent address locations in the RAM. Match operations are performed on the CAM in order to detect the locations of data stored in the RAM. When match data is presented to the CAM, the CAM responds with a xe2x80x9ctagxe2x80x9d representing the address location in RAM containing the desired data. This address location is then driven to the RAM""s address lines in order to access the data.
A conventional content addressable memory has a plurality of word data memories respectively having memory cells, the number of which corresponds to a number of bits of a word. The memory cells are respectively activated by word lines, thereby the data stored in the memory cells are read out respectively via bit lines. Such data read out from the memory cells via the bit lines are respectively supplied to a plurality of match detection-circuits.
Each of the match detection circuits detects whether data on one of the bit lines matches data from a corresponding one of the memory cells, i.e., when a circuit operation signal line which is common to the entire words is in an active state. Each of the match detection circuits activates its corresponding one of match signal lines when the data on the entire bit lines match the data from the memory cells.
When retrieving data in the content addressable memory, the circuit operation signal line needs to be activated, in a state where the word lines are activated and retrieval data are output to the bit signal lines. In this case, if the data stored in the corresponding one of the word data memories, match the retrieval data, its corresponding match detection circuit is activated. By doing this, the data stored in the corresponding one of the word data memories and which match the retrieval data can be extracted. The conventional content addressable memory includes the plurality of match detection circuits respectively corresponding to the word data memories. In this structure, the conventional content addressable memory can simultaneously detect the entire words whether any one of them corresponds to the retrieval data, resulting in retrieving the data at high speed. In this type of content addressable memory, the match detection circuits are operated all at the same time. In such circumstances, a problem occurs in that the content addressable memory consumes a lot of electric power.
Unexamined Japanese Patent Application Kokai Publication No. H9-180468 discloses a content addressable memory, in which data is retrieved in a limited range and a limited number of match detection circuits are activated in order to solve this problem. This content addressable memory has a function for limiting a retrieval range for the following retrieval based on a result of the previous retrieval. In this function, a retrieval range is limited in a series of retrieval processes immediately upon reception of retrieval data, while outputting the word which has been extracted at the end as a retrieval result. In the series of retrieval processes, a retrieval process performed after the retrieval range is further limited is referred to as the xe2x80x9cfollowing retrievalxe2x80x9d, whereas a retrieval process performed before that is referred to as the xe2x80x9cprevious retrievalxe2x80x9d.
The content addressable memory has a memory cell array storing data to be retrieved in the unit of words, an OMEGA-register and a K-register, retaining the retrieval data, a match detection circuit array including match detection circuits independent from each word, a retrieval operation determination circuit and a retrieval range limitation circuit. The memory cell array stores as data to be retrieved a string table, for example, representing a dynamic dictionary and being formed using a data compression algorithm.
In the series of retrieval processes, after the previous retrieval, the content addressable memory processes a result of the previous retrieval and stores the processed data in the registers. Before performing the following retrieval, in the content addressable memory, values (information specifying a retrieval range for the following retrieval based on the result of the previous retrieval) which are stored in the registers are read, and a retrieval range is designated by the retrieval range limitation circuit. Accordingly, in the content addressable memory, a word which is in the first position within the retrieval range for the following retrieval is designated using the result of the previous retrieval.
However, in order for the data stored in the memory cell array to be retrieved based on the retrieval data, in the content addressable memory of the Kokai reference, the time for storing the values based on the result of the previous retrieval and the time for designating a retrieval range after reading the values stored in the registers before the following retrieval are required. Therefore, in the content addressable memory, a problem arises in that the previous retrieval is switched over to the following retrieval with loss of time. Such a content addressable memory requires the registers storing the values of the previous retrieval and the circuit, for processing the values of the previous retrieval in the retrieval range limitation circuit. Obviously, the content addressable memory needs a large space as to include such registers and circuit, and consumes a lot of electric power.
Furthermore, in the content addressable memory of the Kokai reference, of a plurality of obtained retrieval results which are assigned priorities, it is difficult to retrieve a retrieval result having the highest priority, since there is no means for designating priorities for the data. Therefore, in the content addressable memory, in a case where the plurality of retrieval results are obtained, the values to be stored in the registers can not be specified, and the data can not be retrieved after setting a retrieval range.
In unexamined Japanese Patent Application Kokai Publication No. H9-180469 a content addressable memory is disclosed wherein a limited number of match detection circuits are activated. However, in such a content addressable memory, the previous retrieval is switched over to the following retrieval with loss of time, and a register storing values of the previous retrieval is required, and further priorities for data pieces cannot be specified when a plurality of retrieval results are obtained.
U.S. Pat. No. 6,181,592 relates to a technique for retrieving data from a plural pieces of data to be retrieved which matches or is similar to input retrieval data. According to this patent, a memory cell array included in a content addressable memory stores words, as data to be retrieved, respectively at a plurality of addresses, each of which is assigned a priority in a descending order. When the data is input, each of a plurality of match detection circuits detects whether the data matches the words. A plurality of circuits retain, of the retrieval data which have been detected, whether the retrieval data matches the corresponding words by the match detection circuits, data stored at an address which is assigned the highest priority, and outputs the data to a retrieval range designation circuit when the following retrieval beings. The retrieval range designation circuit controls each of mask circuits contained in each of the match detection circuits to be in an active state, thereby designating a retrieval range of words within the memory cell array.
Japanese Patent KOKAI Publication JP-A-62-293596 (1987) discloses a conventional content-addressable memory device wherein one word is composed of n bits. The device comprises a decoder which performs a word selection for writing in n-bit data, a first content-addressable memory cell array in which one word is composed of m bits, a first sensing amplifier for sensing the result of a comparison performed by the first content-addressable memory cell array, a second content addressable memory cell array in which one word is composed of n-m bits for performing a comparison operation using the output of the first sensing amplifier, and a second sensing amplifier for sensing the results of comparison by the second content-addressable memory cell array in dependence upon the output of the first sensing amplifier, whereby it is intended that less power is consumed at the time of the comparison operation.
U.S. Pat. No. 6,081,441 discloses a content-addressable memory wherein match selection circuits are connected to respective ones of match lines connecting corresponding rows of CAM cells associated with word lines. A match selection control circuit, the inputs of which are the word lines, generates match line inhibit signals that inhibit a search when a data search is conducted in the CAM. On the basis of a precharge signal from a control circuit and a match line inhibit signal from the match selection control circuit applied thereto, the match selection circuits inhibit a data search in row-direction CAM cells connected to the match lines that are connected to these match selection circuits, respectively, thereby specifying a data search range in terms of individual word lines. A match line corresponding to each word line in the specified search range attains a non-match state regardless of whether the result of a search is a match or non-match. Thus a data search range is specified by the positions of selected word lines. The number of data search operations is reduced and less power is consumed when the CAM operates.
The content-addressable memory of the ""441 patent functions to input externally applied search data, which comprises a plurality of bits, and to compare the search data with internally stored data to determine if the data matches. The content-addressable memory includes match selection circuits connected to respective ones of match lines, and a match selection control circuit for controlling the match selection circuits. By specifying a search range in units of word lines and inhibiting compare searches in units of word lines that are outside the search range, compare searches are conducted only on the basis of the remaining individual word lines (i.e., only on the word lines within the specified search range).
U.S. Pat. No. 3,648,254 granted to W. F. Beausoleil on Mar. 7, 1972 discloses the implementation of a CAM using shift registers or other rotating media for storage. They are arranged in such a way as to function as a plurality of word-serial searches operating in parallel. It requires that the stored data rotate past the comparator logic, instead of being read from a RAM based on a rotating pointer.
U.S. Pat. No. 4,145,737 granted to S. M. Lamb et al. on Mar. 20, 1979 discloses the implementation of a CAM using RAM for storage. The comparators are a shared resource, but in a search operation, only one RAM location is selected from each block (the same across all blocks).
U.S. Pat. No. 4,622,653 granted to D. J. McElroy on Nov. 11, 1986 discloses a means of integrating comparators together with a DRAM, accessing all cells in a single row of the DRAM simultaneously (a row referred to as a xe2x80x9cblockxe2x80x9d), thereafter comparing them to reference data, with multiple match lines provided for the multiple words in a physical row, and sequential access means for sequencing through all of the blocks that make up the memory.
U.S. Pat. No. 4,958,377 granted to K. Takahashi on Sep. 18, 1990 discloses many possible embodiments of an associative memory, in which data does not need to be explicitly compared, since the value of a bit is encoded in its position.
A paper by M. Motomura et al. entitled xe2x80x9cA 1.2-Million Transistor, 33-MHz, 20-b Dictionary Search Processor (DISP) ULSI with a 160-kb CAMxe2x80x9d, IEEE Journal of Solid-State Circuits, Vol. 25, No. 5, pp. 1158-1165, October 1990, describes a means of sharing a comparator among multiple SRAM cells using categorization, such that a search is completed in a single cycle, but only one of these SRAM cells is actually compared to the reference data (the one belonging to the selected category). The search of stored data is hence only partial. Though SRAM cells and comparators are grouped into blocks, there are no sub-blocks, no parallel searches per block, and only one match line per column. The match line does not perform any access control function.
A paper by G. J. Lipovski entitled xe2x80x9cA Four Megabit Dynamic Systolic Associative Memory Chipxe2x80x9d, Journal of VLSI Signal Processing, Vol. 4, No. 1, p. 3751, 1992 (also U.S. Pat. No. 4,989,180 issued on Jan. 29, 1991), describes a means of storing CAM data in DRAM core cells, which share access to a comparator on a TDM (time division multiplex) basis. The entire contents of the CAM is searched in a single search operation, but the embodiment of this operation is most likely serialized by bit, rather than by word. Row access is controlled by a counter and address signals, rather than shift registers. The plurality of bits belonging to each word are all processed (compared) in the same comparator.
A paper by I. N. Robinson entitled xe2x80x9cPattern-Addressable Memoryxe2x80x9d, IEEE Micro, pp. 20-30, June 1992, describes a structure in which CAM data are stored in DRAM cells, which share a comparator. Access is on a word-by-word basis and is normally performed in some pre-determined order. Rows are selected by address lines and decoders, as controlled by an xe2x80x9carray controllerxe2x80x9d, rather than deterministic ally by shift registers. There is a plurality of blocks on the chip, but each block contains a plurality of complete data words, and blocks are not sub-blocked. Match lines are confined to the xe2x80x9cmatch enginexe2x80x9d associated with each block, and do not run above DRAM cells.
U.S. Pat. No. 4,747,072 granted to I. N. Robinson et al. on May 24, 1988 discloses searching circuitry composed of a plurality of xe2x80x9cretrieval processorsxe2x80x9d, each with an associated bank of RAM. RAM access is controlled by a shift register, thus arbitrating access to the comparator resource in the processor. Although the access pattern, as controlled by the shift register, is sequential, it is not deterministic (fixed TDM). The processor, itself, may contain considerable circuitry in addition to the comparator, for the intended purpose of controlling the search for a sequence of entries, rather than a single isolated entry.
U.S. Pat. No. 4,794,559 granted to A. J. Greenberger on Dec. 27, 1988 discloses a means of achieving content-addressable functionality using standard DRAM storage array(s). Fixed TDM sharing of the comparator may be employed. Though the memory chip may be divided into separate blocks for the purpose of searching multiple words in parallel, these blocks are oriented such that only a single word line is asserted per cycle (said word line spans a plurality of blocks), and the match line is parallel to the word line, rather than parallel to the bit lines.
In a paper by K. J. Schultz et al. entitled xe2x80x9cArchitectures for Large-Capacity CAMsxe2x80x9d, INTEGRATION: the VLSI Journal, Vol. 18, pp. 151-171, 1995 describes, in a general tutorial fashion (pp. 158-161), an architecture employing multiple blocks being searched in parallel.
A significant problem with prior art range matching techniques using CAM cells is that a large number of search operations are required to achieve a single match. A data search in the conventional CAM is carried out for every address and every word and searches may become redundant, or may be performed a number of times equivalent to the number of word lines, depending upon the content of the search data. In other words, if, when data in another memory device is read out using an address that has been detected in the CAM, multiple items of data that have been stored in the memory portions of the CAM cells are identical, searches are conducted until the desired information is obtained and the number of times this is done is the same as the number of identical items of stored data.
Another problem is the flow of unnecessary current, which results in increased power consumption. When a match is obtained as the result of a data search in CAM cells all connected to match lines of associated word lines in a content addressable memory device composed of the conventional CAM cells, the match lines are charged and discharged by the conduction of transistors in the data search portions of the CAM cells. Consequently, the number of words and the bit length are large and an increase in power consumption is the result. The reason for this is that when the results of comparison in regard to an individual word line is indicative of a total match, all of the data search portions of the CAM cells operate, the potential of the match line charged prior to the search operation is discharged and needless power is produced.
Accordingly, the main object of the present invention is to provide a content-addressable memory in which the number of data search operations is reduced and less power is consumed when the CAM operates.
It is another object of the invention to provide a content addressable memory enabling range check for data input which is speedy and avoids the need for data check entry by entry in a multiplicity of cycles.
It is a further object of the invention to provide a range check technique which does not require a large memory space.
It is a further object of the invention to provide a range check technique which does not require multiple access to the stored data table.
It is yet another object of the invention to provide a range check technique which obviates the necessity for multiple entries for each range value and multiple searches for each range value.
It is a further object of the invention to provide a technique for the matching of a data input with a collection of stored data which does not require additional hardware or silicon area thereby reducing the cost of processing.
The range check CAM cell of the invention utilizes a conventional SRAM cell for storage of the data range. The stored data range is determined by the user depending on user requirements. All data whether stored or applied is in binary form. In the basic range check technique of the invention, applied data is compared with stored data bits from the most significant bit (MSB) to the least significant bit (LSB).
While the range check is provided with different cells for upper, lower and equality check, it can also be implemented with only one type of cell, either greater than, equal to, or less than equal by storing appropriate data. The greater than equal to (GTEQ) cell output is true if the stored data is greater than or equal to applied data. Similarly, less than equal to (LTEQ) cell output is true if stored data is less than or equal to applied data.
When comparison is done from MSB to LSB, for LTEQ cell, if the stored data bit is greater than applied the data bit, then stored data is greater than applied data. In such an event, the match line is pulled down and the remaining data bits to be compared are not checked. Again when comparison is done from MSB to LSB, if the stored data bit is less than the applied data bit, for the LTEQ cell, stored data is less than applied data and the remaining bits are not checked. In the case of check for equality or perfect match of applied data with stored data, all bits of stored data and applied data must be equal.
The range check cell of the invention comprises an upper limit field and a lower limit field with a match detector. The range CAM word of the invention facilitates the determination of a range match by comparing incoming data with the Upper and Lower Limit values stored in the range check cell.
In the prior art methods of range check using a SRAM cell simpliciter, each applied data bit was compared with each entry in the stored data. Typically this meant 16 K cycles of comparison for 16 K of applied data and required large amounts of time for comparison. In the present invention, the applied data is compared in parallel with each stored data bit thereby reducing both time taken for comparison and the size of the co-processor.
The upper limit cells in the greater than or equal to range cells (UL[n:0]) comprises of n+1 Upper Limit Range Cells (GTEQ) and stores the upper limit of the range entry contained in the Range Word. The incoming data D[n:0] is compared with the stored value UL[n:0]. When the incoming data is less than or equal to the stored data, the match level is high and the match holds true.
The lower limit field (LL[n:0]) comprises of n+1 lower limit range cells (LTEQ) and stores the lower limit of the range entry contained in the range word. The incoming data D[n:0] is compared with the stored value LL[n:0]. When the stored lower limit of the range entry is less than or equal to the input data bit, the match output is high and the comparison holds true. The match detector ANDS the match outputs from the upper limit and lower limit fields in order to determine the final match for the range CAM word. A sample basic range check cell is given in Table I below.
Table II below provides a sample range check using GTEQ for upper limit and LTEQ for lower limit (for a 16 bit data maximum upper limit=FFFF)
Range check can also be done using GTEQ for both upper and lower limit check. In this case, ones complement (inverted data) is stored in the lower limit. Also ones complement is applied during the range check to the lower limit. (Example: for a 16 bit data the maximum upper limit=FFFF).
Table III provides a representation of such a range check using GTEQ for both upper and lower limit check.
Similarly, basic range check can be done using LTEQ for both upper limit and lower limit. In this case, ones complement (inverted data) is stored in the upper limit. Also ones complement is applied during the range check to the upper limit. (Ex. For 16 bit data maximum upper limit=FFFF). A representation of such a basic range check using a LTEQ cell is provided in Table IV below: